Computer software can be exploited by using mistakes in the processing of input data, which allow an attacker to overwrite executable data (Return Addresses, Function Pointers, jump tables, etc) with data of his choice. The overwritten executable data eventually is loaded into the instruction pointer and the attacker gains control of the application. These exploits are generically known as buffer overflow attacks. A specific type of overflow, known as a stack overflow, overwrites a return address stored on the stack. In general, these attacks are responsible for billions of dollars in damage from malicious users and exploiting the stack is the majority of publicly disclosed exploits in this category.
There are two types of overflow exploit techniques: an adjacent overwrite and a direct overwrite. An adjacent overwrite requires two adjacent memory areas, A and B where B is the target. The data normally is just copied by the program into A but also can accidentally “overflow” into B by some means (i.e. the exploit). This is the “classic” overflow. In a direct overwrite, there are three memory areas required; A and B, which are adjacent and C the ultimate target. C is not required to be adjacent to B or A. This is usually a multi-step affair. An overflow occurs from A into B. B is used by the program later as an address for a data copy. Since B is now defined by the overflow, it can target C and may copy parts of A to it. The attacker has the opportunity to overwrite any location in the process address space. There is not a requirement for the target memory to be adjacent to a data object he has access to. Heap data structure exploits such as double free's are an example of direct overwrite technique.
Most applications today are compiled from a procedure-based language such as C or Java and run on single stack computer architectures (e.g. x86, powerPC, Sparc, ARM, etc). In these environments, sub-routines are invoked by a call instruction (e.g. call, bl, etc), which ultimately stores a return address to the invoking sub-routine onto the stack. The invoked sub-routine sets up a stack frame for local variables, does some work, cleans up the stack frame, and returns to the invoker with a return instruction. The return instruction gets the address of the next instruction from the stack. In some computer architectures (typically RISC), the leaf node of the call graph will not store the return address onto the stack. It will remain in a register but the non-leaf call frames will have stored the return address onto the stack.
The stack exploit modifies the dormant return address stored on the stack. In the stack exploit scenario, the attacker controls the input that is used in one of the overflow techniques above to overwrite the return address on the stack. Now the return instruction fetches the return address stored by the attacker, not what the program stored there. When the return instruction finishes, the attacker will have hijacked the instruction pointer. Then there are many clever ways to continue execution of the hijacked process that have nothing to do with the original function of the application.
Known non-patent documents include:
“The Tao of Windows Buffer Overflow” by Dildog, and posted on the Internet at www.cultdeadcow.com, dated 1999.
An article entitled “Smashing the Stack for Fun and Profit,” by Aleph One, and posted on the internet at http://reactor-core.org/stack-smashing.html discloses a method of overwriting the stack to usurp control of another's computer.
An article by Mike Frantzen and Mike Shuey, entitled “StackGhost: Hardware Facilitated Stack Protection,” available on the Internet at www.stackghost.cerias.purdue.edu, discloses a method of combining an extra piece of hidden information called a cookie with a return address when it is stored on the stack by using an exclusive-or function. It is restored with an exclusive-or using the cookie. In order to successfully overwrite the “encrypted” return address, the attacker must also know the secret cookie. Therefore, a hacker need only obtain the contents of the stack through another means (e.g. a format string attack) to deduce the cookie in order to successfully overwrite the return address. The present invention does not suffer this weakness.
An article by Crispin Cowan et al., entitled “Protecting Systems from Stack Smashing Attacks with StackGuard,” available on the Internet at www.cse.ogi.edu/DISC/projects/immunix discloses a method of adding additional information called a canary to the return address and testing any return address for the presence of the proper canary before allowing a program to continue. The disadvantages to using a canary are that the canary is stored in memory where a hacker can access it and a canary requires the user to recompile applications and libraries, some of which he may not have the source code to do so. The present invention does not require the user to recompile applications or libraries.
Crispin Cowan has also published a technique known as “MemGuard” for preventing return address changes. In MemGuard, individual words of memory can be designated as read-only except when written via a MemGuard API. Memguard's technique is done through an x86 specific set of 4 debug registers and can only protect call trees of 4 or less deep. The present invention is not limited in this regard.
An article from Arash Baratloo et al., entitled “Transparent Run-Time Defense Against Stack Smashing Attacks,” disclose two methods called “Libsafe” and Libverify” that intercept all function calls and check the boundaries of information before storing it on the stack. If the information requested to be stored exceeds the boundary of one stack frame, the information is not stored. These methods guards against overwriting the stack, but do not guard against direct overwrites of memory as does the present invention.
Another method of protecting a computer stack is known as StackShield, which uses a second stack to store copies of return addresses. StackShield requires the user to recompile application and libraries and is susceptible to direct overwrite which the present invention is not.
An article by Livello Avanzato, entitled “Bypassing Stackguard and StackShield,” discloses the disadvantages of Stackguard and StackShield.
An article entitled “RAD: A Compile-Time Solution to Buffer Overflow Attacks,” by Fu-Haw Hsu, discloses a technique of creating a copy of the return address in a separate location that is surrounded by read-only guard pages. Like StackGuard, RAD requires the application to be re-compiled and RAD will not protect against direct overwrites.
An article entitled “Transparent Runtime Shadow Stack: Protection against malicious return address modifications,” discusses prior art methods of preventing buffer overflow that require changes to either the compiler or the hardware, such as Smashguard and StackGhost. The method disclosed essentially consists of verifying the return address before using the return address.
Known patent documents include:
U.S. Pat. No. 4,558,176, entitled “COMPUTER SYSTEMS TO INHIBIT UNAUTHORIZED COPYING, UNAUTHORIZED USAGE, AND AUTOMATED CRACKING OF PROTECTED SOFTWARE,” discloses that information such as return addresses may be encrypted using a secure encryption function, rather than a trivial one such as an exclusive-or function, to prevent a hacker from deducing the encryption key from the encrypted version of the return address and the plaintext version of the return address. U.S. Pat. No. 4,558,176 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Nos. 5,864,707, entitled “SUPERSCALAR MICROPROCESSOR CONFIGURED TO PREDICT RETURN ADDRESSES FROM A RETURN STACK STORAGE”; 5,881,278, entitled “RETURN ADDRESS PREDICTION SYSTEM WHICH ADJUSTS THE CONTENTS OF RETURN STACK STORAGE TO ENABLE CONTINUED PREDICTION AFTER A MISPREDICTED BRANCH”; 5,968,169, entitled “SUPERSCALAR MICROPROCESSOR STACK STRUCTURE FOR JUDGING VALIDITY OF PREDICTED SUBROUTINE RETURN ADDRESSES”; and 6,269,436, entitled “SUPERSCALAR MICROPROCESSOR CONFIGURED TO PREDICT RETURN ADDRESSES FROM A RETURN STACK STORAGE”; disclose methods of using a call tag and a return tag (i.e., canaries) with a return address and comparing the same to predict the return address. The methods of U.S. Pat. Nos. 5,864,707; 5,881,278; 5,968,169; and 6,269,436 have the disadvantages of using a canary as listed above, which the present invention does not. U.S. Pat. Nos. 5,864,707; 5,881,278; 5,968,169; and 6,269,436 are hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,949,973, entitled “METHOD OF RELOCATING THE STACK IN A COMPUTER SYSTEM FOR PREVENTING OVERRATE BY AN EXPLOIT PROGRAM,” discloses a method of relocating the entire stack to a random memory location. The method of U.S. Pat. No. 5,949,973 guards against a direct stack overwrite, but does not guard against an overflow or a write to non-adjacent memory as does the present invention. U.S. Pat. No. 5,949,973 is hereby incorporated by reference into the specification of the present invention. U.S. Pat. No. 6,070,198, entitled “ENCRYPTION WITH A STREAMS-BASED PROTOCOL STACK,” discloses a method of encrypting and decrypting data flowing through the stack. U.S. Pat. No. 6,070,198 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,301,699, entitled “METHOD FOR DETECTING BUFFER OVERFLOW FOR COMPUTER SECURITY,” discloses a method of detecting buffer overflows by determining a plurality of thresholds, analyzing a code to produce a validation value, and comparing the validation value with the thresholds to determine whether a buffer overflow would occur. The method of U.S. Pat. No. 6,301,699 guards against stack overwrite, but does not guard against a direct memory write as does the present invention. U.S. Pat. No. 6,301,699 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,578,094, entitled “METHOD FOR PREVENTING BUFFER OVERFLOW ATTACKS,” discloses a method of having a called procedure determine an upper bound that may be written to a stack allocated array/buffer without overwriting the stack-defined data. Before data is written to the stack, the upper bound is checked, which thereby prevents overwriting data. The present method does not check for an upper bound before writing data to a stack. U.S. Pat. No. 6,578,094 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,618,797, entitled “DEVICE AND METHOD FOR PROTECTION AGAINST STACK OVERFLOW AND FRANKING MACHINE USING SAME,” discloses a method assigning a separate stack for each program part. The method of U.S. Pat. No. 6,618,797 guards against stack overwrite, but not direct memory write. U.S. Pat. No. 6,618,797 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,941,473, entitled “MEMORY DEVICE, STACK PROTECTION SYSTEM, COMPUTER SYSTEM, COMPILER, STACK PROTECTION METHOD, STORAGE MEDIUM AND PROGRAM TRANSMISSION APPARATUS,” discloses a method of using a guard value, or canary, with the return address to guard tampering of the return address. The method of U.S. Pat. No. 6,941,473 has all of the disadvantages of using a canary as listed above, which the present invention does not. U.S. Pat. No. 6,941,473 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,766,513, entitled “METHOD AND SYSTEM OF MEMORY MANAGEMENT USING STACK WALKING,” discloses a method of deleting code from a stack by identifying code to be deleted, checking the frame for a return address to see if it relates to code that should be deleted, and if such a return address is found altering the contents of the stack and the return addresses to point to a correct place and deleting the unneeded code. The method of U.S. Pat. No. 6,766,513 deletes unneeded code, but does not identify which code is unneeded and does not address mismatched call functions. U.S. Pat. No. 6,766,513 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,769,004, entitled “METHOD AND SYSTEM FOR INCREMENTAL STACK SCANNING,” discloses a method of garbage collection wherein the stack scan can be implemented incrementally in units of individual stack location so that scanned portions of the stack do not have to be rescanned if the garbage collector is preempted. The stack scan method disclosed permits scanning the stack from the base of the stack toward the top, or from the top of the stack toward the base, and parses the stack into call frames. The disclosed method records the call frames continuation, so that the correct return location can be determined during an unwind operation. The method of U.S. Pat. No. 6,769,004 guards against stack overwrite for a single stack, but does not guard against stack overwrite using two or more stacks. U.S. Pat. No. 6,769,004 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,996,677, entitled “METHOD AND APPARATUS FOR PROTECTING MEMORY STACKS,” discloses a method of storing the return address in a separate stack upon execution of a jump command. The second stack stores the location on the first stack where the jump occurred and the return address. Before returning from the jump to a subroutine, a comparator is used to compare the return address on the first stack to the return address on the second stack. The method of U.S. Pat. No. 6,996,677 guards against stack overwrite, but does not handle unmatched call returns such as setjump/longjump. U.S. Pat. No. 6,996,677 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,165,150, entitled “RESTRICTING ACCESS TO MEMORY IN A MULTITHREADED ENVIRONMENT,” discloses a method of accessing a buffer without checking for the end of the buffer. The method uses a sentinel word to indicate when data is stored in a different buffer and a single bit to permit/deny checking beyond the apparent end of the buffer. The method of U.S. Pat. No. 7,165,150 does not handle unmatched call returns such as setjump/longjump when unwinding a shadow stack. U.S. Pat. No. 7,165,150 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,178,010, entitled “METHOD AND APPARATUS FOR CORRECTING AN INTERNAL CALL/RETURN STACK IN A MICROPROCESSOR THAT DETECTS FROM MULTIPLE PIPELINE STAGES INCORRECT SPECULATIVE UPDATE OF THE CALL/RETURN STACK,” discloses a method of saving return addresses in different segments of memory. Two stacks are used, the first stores data, and the second stack stores correction information related to call and return instructions. The method of U.S. Pat. No. 7,178,010 does not handle unmatched call returns such as setjump/longjump when unwinding a shadow stack. U.S. Pat. No. 7,178,010 is hereby incorporated by reference into the specification of the present invention.
Known U.S. patent applications include:
U.S. patent application Ser. No. 10/229,712, entitled “METHOD AND PROGRAM FOR INHIBITING ATTACK UPON A COMPUTER,” discloses a method of encrypting the return address in computer memory to prevent a buffer overflow attack. The present invention is not directed toward encrypting the return address in memory. U.S. patent application Ser. No. 10/229,712 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/313,940, entitled “POINTGUARD: METHOD AND SYSTEM FOR PROTECTING PROGRAMS AGAINST POINTER CORRUPTION ATTACKS,” discloses a method of protecting against pointer corruption by encrypting a pointer. The encrypted pointer is decrypted before the pointer is read. The present invention is not directed toward encrypting pointers. U.S. patent application Ser. No. 10/313,940 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/386,709, entitled “METHOD AND APPARATUS FOR CONTROLLING STACK AREA UN MEMORY SPACE,” discloses a method of designating a temporal stack area in which to receive stack overwrites. The method of U.S. patent application Ser. No. 10/386,709 guards against stack overwrites, but does not guard against direct memory writes as does the present invention. U.S. patent application Ser. No. 10/386,709 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/726,229, entitled “APPARATUS, SYSTEM AND METHOD FOR PROTECTING FUNCTION RETURN ADDRESS,” discloses a method of protecting against stack overflow by storing the return address and the stack pointer in a separate stack. The return address is evaluated before executing the return to see if it is a valid return address. No read or write function is permitted to the separate stack, thereby making this second stack secure. The method of U.S. patent application Ser. No. 10/726,229 guards against stack overwrite, but does not guard against set jump/long jump mismatch in the stack. U.S. patent application Ser. No. 10/726,229 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/835,496, entitled “PROGRAM SECURITY THROUGH STACK SEGREGATION,” discloses a method of creating two stacks joined at the base, where protected data is placed in one of the stacks, and unprotected data is placed in the other stack. Protected data, generally frame pointers and return addresses, are placed in the stack that grows downward while unprotected data stack grows upward. While the method of U.S. patent application Ser. No. 10/835,496 guards against most types of stack overflows, the inventor acknowledges that in rare cases an attacker can find and exploit the method in U.S. patent application Ser. No. 10/835,496 by inputting enough data or doing a direct overwrite. Additionally, the method in U.S. patent application Ser. No. 10/835,496 will not work compatibly with asynchronous stack unwinding such as set jump/long jump or structured exception handling. The present invention is designed to detect and correct the situation when an attacker overwrites the return address on the stack correctly handle asynchronous stack unwinding. U.S. patent application Ser. No. 10/835,496 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. Nos. 10/746,667 and 10/644,399, both entitled “METHOD AND APPARATUS TO RETAIN SYSTEM CONTROL WHEN A BUFFER OVERFLOW ATTACK OCCURS,” discloses a method of creating two stacks, wherein the return address is stored on the first stack and the second stack. After a function executes, the method compares the return address on each stack, and if they are the same, returns to that location, otherwise issues a fault. The method described in U.S. patent application Ser. No. 10/644,399 is equivalent to the method described in U.S. Pat. No. 7,178,010 above. The method does not protect against set jump/ long jump where the unmatched call/return function may correctly have different return addresses. U.S. patent application Ser. Nos. 10/746,667 and 10/644,399 are hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/768,750, entitled “METHOD OF PROTECTING A COMPUTER STACK,” discloses a creating two stacks, storing the return address on both stacks, and comparing the two return addresses before returning after completing execution of a subroutine. At least one of the return addresses may be encrypted on the stack. If the two return addresses are not the same, a fault occurs. Although U.S. patent application Ser. No. 10/768,750 protects against stack overflow, it does not address mismatched calls/returns such as set jump/long jump. U.S. patent application Ser. No. 10/768,750 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 10/813,599, entitled “STACK CACHING USING CODE SHARING,” discloses a mixed stack comprising a register stack and a memory stack. Although directed toward virtual machine memory function, the method discloses shift operations at one of the stacks to properly maintain the top of the stack indication. The present method does not pertain to stack state aware translation. U.S. patent application Ser. No. 10/813,599 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 11/014,111, entitled “WRITE PROTECTION OF SUBROUTINE RETURN ADDRESSES,” discloses a method of moving return addresses to the processor and providing a method of write protecting the return addresses to make them non-accessible. The method does not provide a mechanism to fix mismatches in return addresses. U.S. patent application Ser. No. 11/014,111 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 11/095,719, entitled “PROVIDING EXTENDED MEMORY PROTECTION,” discloses a mechanism to make memory locations non-accessible, thereby providing a level of security. The present method does more than just make memory locations non-accessible. U.S. patent application Ser. No. 11/095,719 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application Ser. No. 11/165,268, entitled “METHOD AND APPARATUS FOR MANAGING A LINK RETURN STACK,” discloses a separate stack for return addresses, and a method of identifying misdirected return addresses. Although the method identifies misdirected return addresses, it does not attempt to correct the errant return location. U.S. patent application Ser. No. 11/165,268 is hereby incorporated by reference into the specification of the present invention.
There exists a need to protect information stored on a stack in an easily accessible but unmodifiable location, and to protect the unmatched calls/returns from being overwritten.